// #include <bits/stdc++.h>
// using namespace std;
// using ll=long long;
// int main()
// {
//     string s,ret;
//     //之前数据没有全部读进去，换成这样就可以了
//     while(getline(cin,s))ret+=s;
//     int hash[26];
//     memset(hash,0,sizeof(hash));
//     for(int i=0;i<ret.size();i++)if(ret[i]!=' ')hash[s[i]-'a']++;
//     int maxlen=0,tempi=0;
//     for(int i=0;i<26;i++)
//     {
//         if(hash[i]>maxlen)
//         {
//             maxlen=hash[i];
//             tempi=i;
//         }
//     }
//     // cout<<to_string(tempi+'a')<<endl;
//     printf("%c\n",tempi+'a');
//     return 0;
// }

// #include <bits/stdc++.h>
// using namespace std;
// using ll=long long;
// int main()
// {
//     string s;
//     while(cin>>s)
//     {
//         priority_queue<int,vector<int>,greater<int>> q;
//         unordered_map<char,int> mm;
//         for(int i=0;i<s.size();i++)mm[s[i]]++;
//         for(auto x:mm)q.push(x.second);
//         int sum=0;
//         while(q.size()>1)
//         {
//             int a=q.top();q.pop();
//             int b=q.top();q.pop();
//             sum+=a+b;
//             q.push(a+b);
//         }
//         cout<<sum<<endl;
//     }
//     return 0;
// }

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int n;
int main()
{
    cin>>n;
    //dp[i]表示完全平方数为i的最少个数
    //不选这个数，存在dp[i-1]中，选这个数，dp[i-j*j]
    vector<int> dp(n+1,INT_MAX);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j*j<=i;j++)
            dp[i]=min(dp[i-1],dp[i-j*j]+1);
    }
    cout<<dp[n]<<endl;
    return 0;
}